#include <vector>

using namespace std;

// 求最大公约数、最小公倍数
class Code01_GcdAndLcm
{
	// 证明辗转相除法就是证明如下关系：
	// gcd(a, b) = gcd(b, a % b)
	// 假设 a % b = r，即需要证明的关系为：gcd(a, b) = gcd(b, r)
	// 证明过程：
	// 因为 a % b = r，所以如下两个等式必然成立
	// 1) a = b * q + r，q为0、1、2、3....中的一个整数
	// 2) r = a − b * q，q为0、1、2、3....中的一个整数
	// 假设 u 是 a 和 b 的公因子，则有: a = s * u, b = t * u
	// 把 a 和 b 代入 2) 得到，r = s * u - t * u * q = (s - t * q) * u
	// 这说明 : u 如果是 a 和 b 的公因子，那么 u 也是 r 的因子
	// 假设 v 是 b 和 r 的公因子，则有: b = x * v, r = y * v
	// 把 b 和 r 代入 1) 得到，a = x * v * q + y * v = (x * q + y) * v
	// 这说明 : v 如果是 b 和 r 的公因子，那么 v 也是 a 的公因子
	// 综上，a 和 b 的每一个公因子 也是 b 和 r 的一个公因子，反之亦然
	// 所以，a 和 b 的全体公因子集合 = b 和 r 的全体公因子集合
	// 即 gcd(a, b) = gcd(b, r)
	// 证明结束

    static long gcd(long a, long b)
    {
        return b == 0 ? a : gcd(b, a % b);
    }

    static long lcm(long a, long b)
    {
        return (long)a / gcd(a, b) * b; 
    }

};